/*
二维前缀和：
    给定二维数组g[n][m]，m次询问，每次求区间上各元素之和，如求[(1,1),(2,2)]就是求g[1][1]+g[1][2]+g[2][1]+g[2][2]。
*/

#include <bits/stdc++.h>
using namespace std;
const int n = 3, m = 4;
int g[n][m] = {
    {1, 5, 6, 8},
    {9, 6, 7, 3},
    {5, 3, 2, 4}};
int sum[n][m];
void pre_sum()
{
    sum[0][0] = g[0][0];
    for (int i = 1; i < n; i++)
        sum[i][0] = sum[i - 1][0] + g[i][0];
    for (int j = 1; j < m; j++)
        sum[0][j] = sum[0][j - 1] + g[0][j];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + g[i][j];
}
int get_sum(int x1, int y1, int x2, int y2)
{

    if (x1 == 0 && y1 == 0)
        return sum[x2][y2];
    if (y1 == 0)
        return sum[x2][y2] - sum[x1 - 1][y2];
    if (x1 == 0)
        return sum[x2][y2] - sum[x2][y1 - 1];
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
int main()
{
    memset(sum, 0, sizeof(sum));
    pre_sum();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << sum[i][j] << " ";
        cout << endl;
    }
    cout << get_sum(1, 1, 2, 2) << " " << get_sum(0, 1, 1, 3) << endl;
    return 0;
}
